package de.tuberlin.dima.dkey.server;

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;

import org.apache.log4j.Logger;

import com.google.gson.JsonArray;
import com.google.gson.JsonElement;
import com.google.gson.JsonObject;
import com.google.gson.JsonParser;

import de.tuberlin.dima.dkey.util.GConfig;
import de.tuberlin.dima.dkey.util.GEdge;
import de.tuberlin.dima.dkey.nodes.GNode;
import de.tuberlin.dima.dkey.util.GraphViz;
import de.tuberlin.dima.dkey.util.HashSetSorter;
import de.tuberlin.dima.dkey.nodes.WordNode;

public class GQuery {

	static Logger logger = Logger.getLogger(GQuery.class);

	private LinkedList<GNode> nodeList = new LinkedList<GNode>();

	private LinkedList<GEdge> edgeList = new LinkedList<GEdge>();

	int idcounter = 0;

	private GConfig config = null;
	
	public GQuery(){
		config = new GConfig();
		config.setRemoveCapitalisation(true);
	}
	
	//public GQuery(GConfig config){
	//	this.config = config;
	//}


	public String readJson(String treeJson){
		
		JsonParser parser = new JsonParser();
		JsonArray array;

		try{
			array = parser.parse(treeJson).getAsJsonObject().get("graphs").getAsJsonArray();
		}catch(IllegalStateException e){
			logger.error("JSon Parser Error: " + e);
			return "{\"error\": \"JSon Parser Error: " + e +"\"}";
		}
		
		for (int i =0 ; i < array.size();i++){
			//Looping through the graphs now

			JsonObject graph = array.get(i).getAsJsonObject();
			
			HashMap<Integer, GNode> tmpList = new HashMap<Integer, GNode>();
			for (JsonElement node : graph.get("nodes").getAsJsonArray()){

				try {
					
					GNode tmpNode;
					
					@SuppressWarnings("rawtypes")
					Class cls = Class.forName("de.tuberlin.dima.dkey.nodes." + node.getAsJsonObject().get("type").getAsString());
					tmpNode = (GNode) cls.getConstructors()[1].newInstance(graph.get("id").getAsInt(), node.getAsJsonObject().get("id").getAsInt(), node.getAsJsonObject().get("value").getAsString());
					//GNode tmpNode = new WordNode(graph.get("id").getAsInt(), node.getAsJsonObject().get("id").getAsInt(), node.getAsJsonObject().get("value").getAsString());
					tmpList.put(node.getAsJsonObject().get("id").getAsInt(), tmpNode);
					
					
					this.addBaseNode(tmpNode);
				
				} catch (Exception e) {
					e.printStackTrace();
				}

			}
			
			//System.out.println(graph.get("edges").getAsJsonArray() );
			for (JsonElement edge : graph.get("edges").getAsJsonArray()){
					this.addBaseEdge(tmpList.get(edge.getAsJsonObject().get("source").getAsInt()), tmpList.get(edge.getAsJsonObject().get("sink").getAsInt()));
			}
			
		}

		return "Ok";
		
	}
	
	private GNode addBaseNode(GNode node) {
		nodeList.add(node);
		return node;
	}

	private GEdge addBaseEdge(GNode source, GNode sink) {
		GEdge edge = new GEdge(-1, source.getId(), sink.getId());
		edgeList.add(edge);
		return edge;
	}


	
	public LinkedList<GNode> rootNode(LinkedList<GNode> nodeL, LinkedList<GEdge> edgeL){
		//This is not very good and not very fast 
		HashMap<Integer,Boolean> idList = new HashMap<Integer,Boolean>();
		
		for (GNode node :  nodeL){
			if (!idList.containsKey(node.getId())){
				idList.put(node.getId(), true);
			}
			
		}
		
		for (GEdge edge : edgeL){
			if(idList.containsKey(edge.getSink())){
				idList.put(edge.getSink(), false) ;
			}
		}
		
		LinkedList<GNode> returnList = new LinkedList<GNode>();
		
		for(Integer i : idList.keySet()){
			if (idList.get(i) == true){
				returnList.add( searchForNodeInNodeList(nodeL, i) );
			}
		}
		
		//If there was no root make it crash and burn
		//Idiot user
		if(returnList.size() ==0 )
			return null;
		
		return returnList;
	}
	
	public LinkedList<Integer> execute (TreeDB g){
		/*
		 * Graph Selection
		 */
				
		//Find all the graphs that have the keywords
		HashMap<String , HashSet<Integer>> gNodeList = g.getNodeList();

		//Using the size of the query tree is a little excessive but it can never be bigger than this
		LinkedList<HashSet<Integer>> graphsSelected = new LinkedList<HashSet<Integer>>();

		//long time = System.currentTimeMillis();
				

		for (GNode node : this.nodeList){
			for(String index : node.getIndexValues()){
				if (!gNodeList.containsKey(index)){
					//We assume that if the nodes in the query are not in the 
					//graphs we don't need to continue

					//if (node instanceof GNodeRegex){
					//	At some stage we should do the regex on the keyspace here	
					//}else{
					logger.debug("There is no such item in any graph: " + index);
					return new LinkedList<Integer>();
					//}
				}else{
					//If the list is already in the collection don't add it
					if ( ! graphsSelected.contains(gNodeList.get(index))){
						graphsSelected.add(gNodeList.get(index ) );
					}
				}
			}
		}
		
		//System.out.println("Graphlist creation took " + (System.currentTimeMillis() - time) + " milliseconds");
		//time = System.currentTimeMillis();

		//Order them so the merging is faster
		Collections.sort(graphsSelected, new HashSetSorter());
		graphsSelected.addFirst(graphsSelected.pollLast());
				
		//Now we come to the Merging
		for(;;){
			if(graphsSelected.size() == 1){
				break;
			}
			
			
			HashSet<Integer> first = graphsSelected.pollFirst();
			HashSet<Integer> second = graphsSelected.pollFirst();
			HashSet<Integer> result = new HashSet<Integer>();
			for (int item : first){
				if(second.contains(item)){
					result.add(item);
				}
			}
			graphsSelected.addFirst(result);
		}
		
		if(graphsSelected.size() != 1){
			logger.fatal("Somehow the result list is too big (!=1) This is really bad");
			System.exit(1);
		}

		//System.out.println("Merlist merging took " + (System.currentTimeMillis() - time) + " milliseconds");
		//time = System.currentTimeMillis();

		
		//So now we have a list of Graphs we have to check if the correct edges exist
		logger.debug("We will look at following trees: " + graphsSelected);
		
		/*
		 * Edge checking
		 */
		
		
		//Get only the Graphs we need
		HashMap<Integer, LinkedList<GEdge>> edgeList = new HashMap<Integer, LinkedList<GEdge>>();  

		for (Integer graph : graphsSelected.getFirst()){
			edgeList.put(graph, g.getEdgeList().get(graph));
		}
		
		LinkedList<Integer> results = new LinkedList<Integer>();
		
		
		LinkedList<GNode> queryNodes = this.rootNode(this.nodeList, this.edgeList);
		
		logger.debug("The query root node was selected as: " + queryNodes);
		
		//Check if we got a root node back
		if(queryNodes == null){
			logger.warn("Not really possible to do a query without root");
			return new LinkedList<Integer>();
		}
		
		if(queryNodes.size() != 1){
			logger.warn("We don't support more than 2 disjoint graphs");
			return new LinkedList<Integer>();
		}

		for (Integer graph : graphsSelected.getFirst()){
			//Boolean isCorrect = true;
			
			//Get the rootnode for the grpah
			LinkedList<GNode> graphRoot = rootNode(g.getGraphNodeList().get(graph), g.getEdgeList().get(graph));
			
			if(graphRoot == null){
				logger.info("Selected graph has no root: " + graph);
				continue;
			}
			
			if(graphRoot.size() !=1){
				logger.info("Selected graph has more than one root:" + graph);
				continue;
			}
			
			for (GNode queryNode : queryNodes){
				if (matchTrees(queryNode, graphRoot.getFirst(), this.nodeList, this.edgeList, g.getGraphNodeList().get(graph), g.getEdgeList().get(graph))){	
					if(results.size() >= 20){
		            	logger.info("Only returned the first 20 Elements");
						return results;
					}
					results.add(graph);						
				}
			}
		}
		
		//System.out.println("Tree matching took " + (System.currentTimeMillis() - time) + " milliseconds");
		//time = System.currentTimeMillis();

		
		return results;
	}

	
	private boolean matchTrees(GNode queryNode, GNode checkNode, LinkedList<GNode> queryNodes, LinkedList<GEdge> queryEdges, LinkedList<GNode> checkNodes, LinkedList<GEdge> checkEdges ){
		//Check if the values are the same
		//System.out.println( queryNode.getValue() + " : " + checkNode.getValue());
		if(!checkNode.equals(queryNode)){
			return false;
		}
		
		if(getChildren(queryNodes, queryEdges, queryNode).isEmpty()){
			//Because there are no children in the query and the values are the same
			return true;
		}
		
		//Now check the children
		for (GNode queryChildren : getChildren(queryNodes, queryEdges, queryNode)){
			boolean hasChild = false;
			for (GNode checkChildren : getChildren(checkNodes, checkEdges, checkNode)){
				if(matchTrees(queryChildren,checkChildren, queryNodes, queryEdges, checkNodes,checkEdges  )){
					hasChild = true;
				}
			}
			if(!hasChild){
				return false;
			}
		}
		
		return true;
	}
	
	public GNode searchForNodeInNodeList(LinkedList<GNode> list, int id){
		for(GNode node : list){
			if(node.getId() == id)
				return node;
		}
		return null;
	}
	
	public LinkedList<GNode> getChildren(LinkedList<GNode>nodeList, LinkedList<GEdge> edgeList, GNode node){
		
		LinkedList<Integer> resultEdges = new LinkedList<Integer>();
		
		for (GEdge edge : edgeList){
			if (edge.getSource() == node.getId()){
				resultEdges.add(edge.getSink() );
			}
		}
		LinkedList<GNode> resultNodes = new LinkedList<GNode>();
		
		for(GNode snode : nodeList){
			if( resultEdges.contains(snode.getId()) ){
				resultNodes.add(snode);
			}
		}
		
		return resultNodes;
	}
	
	/**
	 * Prints a png of the tree
	 * Mainly for debug reasons
	 * 
	 * @param File Obj (please name the file .png otherwise there might be problems)
	 */
	public void paint(File out) {
		GraphViz gv = new GraphViz();
		gv.addln(gv.start_graph());
		for (GNode node : nodeList) {
			gv.addln("node" + node.getId() + "  [color="+ node.getColour() +" label=\"" + node.getId() +":"+ node.getValue() + " \"];");
		}

		for (GEdge edge : edgeList) {
			gv.addln("node" + edge.getSource() + "-> node" + edge.getSink());
		}
		gv.addln("}");

		gv.addln(gv.end_graph());

		//System.out.println(gv.getDotSource());
		
		String type = "png";
		//new File(fileName + "." + type);
		gv.writeGraphToFile(gv.getGraph(gv.getDotSource(), type), out);

	}

}
